package com.zk.algorithm.tree;

import com.zk.algorithm.annotation.Easy;
import com.zk.algorithm.annotation.LeetCodeExplore;
import com.zk.algorithm.bean.TreeNode;

/**
 * 转为平衡二叉树
 *
 * @author zk
 */
@LeetCodeExplore
@Easy
public class ConvertSortedArraytoBinarySearchTree {

    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }

        return getTreeNode(nums, 0, nums.length - 1);
    }

    private TreeNode getTreeNode(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }

        //        [左,中,右]
        // [左,中,右]    [左,中,右]
        int middle = start + (end - start) / 2;
        TreeNode n = new TreeNode(nums[middle]);
        n.left = getTreeNode(nums, start, middle - 1);
        n.right = getTreeNode(nums, middle + 1, end);
        return n;
    }

}
